package com.leetcode.algorithm.y22.m09.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 * 
 * https://leetcode.cn/problems/binary-tree-maximum-path-sum/
 *  
 * @author jie.deng
 *
 */
class Question0124Solution01 {

	public int maxPathSum(TreeNode root) {
		int[] maxPathSumArr = new int[] { Integer.MIN_VALUE };
		dfs(root, maxPathSumArr);
		return maxPathSumArr[0];
	}

	/**
	 * 
	 * @param root
	 * @param maxPathSumArr
	 * @return 路径以root为端点的路径和
	 */
	private int dfs(TreeNode root, int[] maxPathSumArr) {
		int left = 0;
		if (root.left != null) {
			left = dfs(root.left, maxPathSumArr);
		}
		if (left < 0) {
			left = 0;
		}
		int right = 0;
		if (root.right != null) {
			right = dfs(root.right, maxPathSumArr);
		}
		if (right < 0) {
			right = 0;
		}
		if (left + root.val + right > maxPathSumArr[0]) {
			maxPathSumArr[0] = left + root.val + right;
		}
		return Math.max(left, right) + root.val;
	}

}